home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / newsgate / regex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-18  |  18.8 KB  |  871 lines
  1. #if    !defined(lint) && !defined(SABER)
  2. static char RCS[] =
  3.     "$Header: /nfs/papaya/u2/rsalz/src/newsgate/RCS/regex.c,v 1.4 91/07/18 11:04:38 rsalz Exp $";
  4. #endif    /* !defined(lint) && !defined(SABER) */
  5. /*
  6.  * regex - Regular expression pattern matching
  7.  *         and replacement
  8.  *
  9.  *
  10.  * By:  Ozan S. Yigit (oz)
  11.  *      Dept. of Computer Science
  12.  *      York University
  13.  *
  14.  *
  15.  * These routines are the PUBLIC DOMAIN equivalents 
  16.  * of regex routines as found in 4.nBSD UN*X, with minor
  17.  * extensions.
  18.  *
  19.  * These routines are derived from various implementations
  20.  * found in software tools books, and Conroy's grep. They
  21.  * are NOT derived from licensed/restricted software.
  22.  * For more interesting/academic/complicated implementations,
  23.  * see Henry Spencer's regexp routines, or GNU Emacs pattern
  24.  * matching module.
  25.  *
  26.  * Routines:
  27.  *      re_comp:        compile a regular expression into
  28.  *                      a DFA.
  29.  *
  30.  *            char *re_comp(s)
  31.  *            char *s;
  32.  *
  33.  *      re_exec:        execute the DFA to match a pattern.
  34.  *
  35.  *            int re_exec(s)
  36.  *            char *s;
  37.  *
  38.  *    re_modw        change re_exec's understanding of what
  39.  *            a "word" looks like (for \< and \>)
  40.  *            by adding into the hidden word-character 
  41.  *            table.
  42.  *
  43.  *            void re_modw(s)
  44.  *            char *s;
  45.  *
  46.  *      re_subs:    substitute the matched portions in
  47.  *                  a new string.
  48.  *
  49.  *            int re_subs(src, dst)
  50.  *            char *src;
  51.  *            char *dst;
  52.  *
  53.  *    re_fail:    failure routine for re_exec.
  54.  *
  55.  *            void re_fail(msg, op)
  56.  *            char *msg;
  57.  *            char op;
  58.  *  
  59.  * Regular Expressions:
  60.  *
  61.  *      [1]     char    matches itself, unless it is a special
  62.  *                      character (metachar): . \ [ ] * + ^ $
  63.  *
  64.  *      [2]     .       matches any character.
  65.  *
  66.  *      [3]     \       matches the character following it, except
  67.  *            when followed by a left or right round bracket,
  68.  *            a digit 1 to 9 or a left or right angle bracket. 
  69.  *            (see [7], [8] and [9])
  70.  *            It is used as an escape character for all 
  71.  *            other meta-characters, and itself. When used
  72.  *            in a set ([4]), it is treated as an ordinary
  73.  *            character.
  74.  *
  75.  *      [4]     [set]   matches one of the characters in the set.
  76.  *                      If the first character in the set is "^",
  77.  *                      it matches a character NOT in the set. A
  78.  *                      shorthand S-E is used to specify a set of
  79.  *                      characters S upto E, inclusive. The special
  80.  *                      characters "]" and "-" have no special
  81.  *                      meaning if they appear as the first chars
  82.  *                      in the set.
  83.  *                      examples:        match:
  84.  *
  85.  *                              [a-z]    any lowercase alpha
  86.  *
  87.  *                              [^]-]    any char except ] and -
  88.  *
  89.  *                              [^A-Z]   any char except uppercase
  90.  *                                       alpha
  91.  *
  92.  *                              [a-zA-Z] any alpha
  93.  *
  94.  *      [5]     *       any regular expression form [1] to [4], followed by
  95.  *                      closure char (*) matches zero or more matches of
  96.  *                      that form.
  97.  *
  98.  *      [6]     +       same as [5], except it matches one or more.
  99.  *
  100.  *      [7]             a regular expression in the form [1] to [10], enclosed
  101.  *                      as \(form\) matches what form matches. The enclosure
  102.  *                      creates a set of tags, used for [8] and for
  103.  *                      pattern substution. The tagged forms are numbered
  104.  *            starting from 1.
  105.  *
  106.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  107.  *                      previously tagged regular expression ([7]) matched.
  108.  *
  109.  *    [9]    \<    a regular expression starting with a \< construct
  110.  *        \>    and/or ending with a \> construct, restricts the
  111.  *            pattern matching to the beginning of a word, and/or
  112.  *            the end of a word. A word is defined to be a character
  113.  *            string beginning and/or ending with the characters
  114.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  115.  *            followed by any character outside those mentioned.
  116.  *
  117.  *      [10]            a composite regular expression xy where x and y
  118.  *                      are in the form [1] to [10] matches the longest
  119.  *                      match of x followed by a match for y.
  120.  *
  121.  *      [11]    ^    a regular expression starting with a ^ character
  122.  *        $    and/or ending with a $ character, restricts the
  123.  *                      pattern matching to the beginning of the line,
  124.  *                      or the end of line. [anchors] Elsewhere in the
  125.  *            pattern, ^ and $ are treated as ordinary characters.
  126.  *
  127.  *
  128.  * Acknowledgements:
  129.  *
  130.  *    HCR's Hugh Redelmeier has been most helpful in various
  131.  *    stages of development. He convinced me to include BOW
  132.  *    and EOW constructs, originally invented by Rob Pike at
  133.  *    the University of Toronto.
  134.  *
  135.  * References:
  136.  *              Software tools            Kernighan & Plauger
  137.  *              Software tools in Pascal        Kernighan & Plauger
  138.  *              Grep [rsx-11 C dist]            David Conroy
  139.  *        ed - text editor        Un*x Programmer's Manual
  140.  *        Advanced editing on Un*x    B. W. Kernighan
  141.  *        RegExp routines            Henry Spencer
  142.  *
  143.  * Notes:
  144.  *
  145.  *    This implementation uses a bit-set representation for character
  146.  *    classes for speed and compactness. Each character is represented 
  147.  *    by one bit in a 128-bit block. Thus, CCL or NCL always takes a 
  148.  *    constant 16 bytes in the internal dfa, and re_exec does a single
  149.  *    bit comparison to locate the character in the set.
  150.  *
  151.  * Examples:
  152.  *
  153.  *    pattern:    foo*.*
  154.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  155.  *    matches:    fo foo fooo foobar fobar foxx ...
  156.  *
  157.  *    pattern:    fo[ob]a[rz]    
  158.  *    compile:    CHR f CHR o CCL 2 o b CHR a CCL bitset END
  159.  *    matches:    fobar fooar fobaz fooaz
  160.  *
  161.  *    pattern:    foo\\+
  162.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  163.  *    matches:    foo\ foo\\ foo\\\  ...
  164.  *
  165.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  166.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  167.  *    matches:    foo1foo foo2foo foo3foo
  168.  *
  169.  *    pattern:    \(fo.*\)-\1
  170.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  171.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  172.  * 
  173.  */
  174.  
  175. #define MAXDFA  1024
  176. #define MAXTAG  10
  177.  
  178. #define OKP     1
  179. #define NOP     0
  180.  
  181. #define CHR     1
  182. #define ANY     2
  183. #define CCL     3
  184. #define NCL     4
  185. #define BOL     5
  186. #define EOL     6
  187. #define BOT     7
  188. #define EOT     8
  189. #define BOW    9
  190. #define EOW    10
  191. #define REF     11
  192. #define CLO     12
  193.  
  194. #define END     0
  195.  
  196. /*
  197.  * The following defines are not meant
  198.  * to be changeable. They are for readibility
  199.  * only.
  200.  *
  201.  */
  202. #define MAXCHR    128
  203. #define CHRBIT    8
  204. #define BITBLK    MAXCHR/CHRBIT
  205. #define BLKIND    0170
  206. #define BITIND    07
  207.  
  208. #define ASCIIB    0177
  209.  
  210. typedef /*unsigned*/ char CHAR;
  211.  
  212. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  213. static CHAR dfa[MAXDFA];        /* automaton..       */
  214. static int  sta = NOP;                   /* status of lastpat */
  215.  
  216. static CHAR bittab[BITBLK];        /* bit table for CCL */
  217.  
  218. static void
  219. chset(c) register CHAR c; { bittab[((c)&BLKIND)>>3] |= 1<<((c)&BITIND); }
  220.  
  221. #define badpat(x)    return(*dfa = END, x)
  222. #define store(x)    *mp++ = x
  223.  
  224. char *     
  225. re_comp(pat)
  226. char *pat;
  227. {
  228.     register char *p;               /* pattern pointer   */
  229.     register CHAR *mp=dfa;          /* dfa pointer       */
  230.     register CHAR *lp;              /* saved pointer..   */
  231.     register CHAR *sp=dfa;          /* another one..     */
  232.  
  233.     register int tagi = 0;          /* tag stack index   */
  234.     register int tagc = 1;          /* actual tag count  */
  235.  
  236.     register int n;
  237.     int c1, c2;
  238.         
  239.     if (!pat || !*pat)
  240.         if (sta)
  241.             return(0);
  242.         else
  243.             badpat("No previous regular expression");
  244.     sta = NOP;
  245.  
  246.     for (p = pat; *p; p++) {
  247.         lp = mp;
  248.         switch(*p) {
  249.  
  250.         case '.':               /* match any char..  */
  251.             store(ANY);
  252.             break;
  253.  
  254.         case '^':               /* match beginning.. */
  255.             if (p == pat)
  256.                 store(BOL);
  257.             else {
  258.                 store(CHR);
  259.                 store(*p);
  260.             }
  261.             break;
  262.  
  263.         case '$':               /* match endofline.. */
  264.             if (!*(p+1))
  265.                 store(EOL);
  266.             else {
  267.                 store(CHR);
  268.                 store(*p);
  269.             }
  270.             break;
  271.  
  272.         case '[':               /* match char class..*/
  273.  
  274.             if (*++p == '^') {
  275.                 store(NCL);
  276.                 p++;
  277.             }
  278.             else
  279.                 store(CCL);
  280.  
  281.             if (*p == '-')        /* real dash */
  282.                 chset(*p++);
  283.             if (*p == ']')        /* real brac */
  284.                 chset(*p++);
  285.             while (*p && *p != ']') {
  286.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  287.                     p++;
  288.                     c1 = *(p-2) + 1;
  289.                     c2 = *p++;
  290.                     while (c1 <= c2)
  291.                         chset(c1++);
  292.                 }
  293. #if    defined(EXTEND)
  294.                 else if (*p == '\\' && *(p+1)) {
  295.                     p++;
  296.                     chset(*p++);
  297.                 }
  298. #endif    /* defined(EXTEND) */
  299.                 else
  300.                     chset(*p++);
  301.             }
  302.             if (!*p)
  303.                 badpat("Missing ]");
  304.  
  305.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  306.                 store(bittab[n]);
  307.     
  308.             break;
  309.  
  310.         case '*':               /* match 0 or more.. */
  311.         case '+':               /* match 1 or more.. */
  312.             if (p == pat)
  313.                 badpat("Empty closure");
  314.             lp = sp;                /* previous opcode */
  315.             if (*lp == CLO)         /* equivalence..   */
  316.                 break;
  317.             switch(*lp) {
  318.  
  319.             case BOL:
  320.             case BOT:
  321.             case EOT:
  322.             case BOW:
  323.             case EOW:
  324.             case REF:
  325.                 badpat("Illegal closure");
  326.             default:
  327.                 break;
  328.             }
  329.  
  330.             if (*p == '+')
  331.                 for (sp = mp; lp < sp; lp++)
  332.                     store(*lp);
  333.  
  334.             store(END);
  335.             store(END);
  336.             sp = mp;
  337.             while (--mp > lp)
  338.                 *mp = mp[-1];
  339.             store(CLO);
  340.             mp = sp;
  341.             break;
  342.  
  343.         case '\\':              /* tags, backrefs .. */
  344.             switch(*++p) {
  345.  
  346.             case '(':
  347.                 if (tagc < MAXTAG) {
  348.                     tagstk[++tagi] = tagc;
  349.                     store(BOT);
  350.                     store(tagc++);
  351.                 }
  352.                 else
  353.                     badpat("Too many \\(\\) pairs");
  354.                 break;
  355.             case ')':
  356.                 if (*sp == BOT)
  357.                     badpat("Null pattern inside \\(\\)");
  358.                 if (tagi > 0) {
  359.                     store(EOT);
  360.                     store(tagstk[tagi--]);
  361.                 }
  362.                 else
  363.                     badpat("Unmatched \\)");
  364.                 break;
  365.             case '<':
  366.                 store(BOW);
  367.                 break;
  368.             case '>':
  369.                 if (*sp == BOW)
  370.                     badpat("Null pattern inside \\<\\>");
  371.                 store(EOW);
  372.                 break;
  373.             case '1':
  374.             case '2':
  375.             case '3':
  376.             case '4':
  377.             case '5':
  378.             case '6':
  379.             case '7':
  380.             case '8':
  381.             case '9':
  382.                 n = *p-'0';
  383.                 if (tagi > 0 && tagstk[tagi] == n)
  384.                     badpat("Cyclical reference");
  385.                 if (tagc > n) {
  386.                     store(REF);
  387.                     store(n);
  388.                 }
  389.                 else
  390.                     badpat("Undetermined reference");
  391.                 break;
  392. #if    defined(EXTEND)
  393.             case 'b':
  394.                 store(CHR);
  395.                 store('\b');
  396.                 break;
  397.             case 'n':
  398.                 store(CHR);
  399.                 store('\n');
  400.                 break;
  401.             case 'f':
  402.                 store(CHR);
  403.                 store('\f');
  404.                 break;
  405.             case 'r':
  406.                 store(CHR);
  407.                 store('\r');
  408.                 break;
  409.             case 't':
  410.                 store(CHR);
  411.                 store('\t');
  412.                 break;
  413. #endif    /* defined(EXTEND) */
  414.             default:
  415.                 store(CHR);
  416.                 store(*p);
  417.             }
  418.             break;
  419.  
  420.         default :               /* an ordinary char  */
  421.             store(CHR);
  422.             store(*p);
  423.             break;
  424.         }
  425.         sp = lp;
  426.     }
  427.     if (tagi > 0)
  428.         badpat("Unmatched \\(");
  429.     store(END);
  430.     sta = OKP;
  431.     return(0);
  432. }
  433.  
  434.  
  435. static char *bol;
  436. static char *bopat[MAXTAG];
  437. static char *eopat[MAXTAG];
  438. static char *pmatch();
  439.  
  440. /*
  441.  * re_exec:
  442.  *     execute dfa to find a match.
  443.  *
  444.  *    special cases: (dfa[0])    
  445.  *        BOL
  446.  *            Match only once, starting from the
  447.  *            beginning.
  448.  *        CHR
  449.  *            First locate the character without
  450.  *            calling pmatch, and if found, call
  451.  *            pmatch for the remaining string.
  452.  *        END
  453.  *            re_comp failed, poor luser did not
  454.  *            check for it. Fail fast.
  455.  *
  456.  *    If a match is found, bopat[0] and eopat[0] are set
  457.  *    to the beginning and the end of the matched fragment,
  458.  *    respectively.
  459.  *
  460.  */
  461.  
  462. int
  463. re_exec(lp)
  464. register char *lp;
  465. {
  466.     register char c;
  467.     register char *ep = 0;
  468.     register CHAR *ap = dfa;
  469.  
  470.     bol = lp;
  471.  
  472.     bopat[0] = 0;
  473.     bopat[1] = 0;
  474.     bopat[2] = 0;
  475.     bopat[3] = 0;
  476.     bopat[4] = 0;
  477.     bopat[5] = 0;
  478.     bopat[6] = 0;
  479.     bopat[7] = 0;
  480.     bopat[8] = 0;
  481.     bopat[9] = 0;
  482.  
  483.     switch(*ap) {
  484.  
  485.     case BOL:            /* anchored: match from BOL only */
  486.         ep = pmatch(lp,ap);
  487.         break;
  488.     case CHR:            /* ordinary char: locate it fast */
  489.         c = *(ap+1);
  490.         while (*lp && *lp != c)
  491.             lp++;
  492.         if (!*lp)        /* if EOS, fail, else fall thru. */
  493.             return(0);
  494.     default:            /* regular matching all the way. */
  495.         while (*lp) {
  496.             if ((ep = pmatch(lp,ap)) != 0)
  497.                 break;
  498.             lp++;
  499.         }
  500.         break;
  501.     case END:            /* munged automaton. fail always */
  502.         return(0);
  503.     }
  504.     if (!ep)
  505.         return(0);
  506.  
  507.     bopat[0] = lp;
  508.     eopat[0] = ep;
  509.     return(1);
  510. }
  511.  
  512. /* 
  513.  * pmatch: 
  514.  *    internal routine for the hard part
  515.  *
  516.  *     This code is mostly snarfed from an early
  517.  *     grep written by David Conroy. The backref and
  518.  *     tag stuff, and various other mods are by oZ.
  519.  *
  520.  *    special cases: (dfa[n], dfa[n+1])
  521.  *        CLO ANY
  522.  *            We KNOW ".*" will match ANYTHING
  523.  *            upto the end of line. Thus, go to
  524.  *            the end of line straight, without
  525.  *            calling pmatch recursively. As in
  526.  *            the other closure cases, the remaining
  527.  *            pattern must be matched by moving
  528.  *            backwards on the string recursively,
  529.  *            to find a match for xy (x is ".*" and 
  530.  *            y is the remaining pattern) where
  531.  *            the match satisfies the LONGEST match
  532.  *            for x followed by a match for y.
  533.  *        CLO CHR
  534.  *            We can again scan the string forward
  535.  *            for the single char without recursion, 
  536.  *            and at the point of failure, we execute 
  537.  *            the remaining dfa recursively, as
  538.  *            described above.
  539.  *
  540.  *    At the end of a successful match, bopat[n] and eopat[n]
  541.  *    are set to the beginning and end of subpatterns matched
  542.  *    by tagged expressions (n = 1 to 9).    
  543.  *
  544.  */
  545.  
  546. extern void re_fail();
  547.  
  548. /*
  549.  * character classification table for word boundary
  550.  * operators BOW and EOW. the reason for not using 
  551.  * ctype macros is that we can let the user add into 
  552.  * our own table. see re_modw. This table is not in
  553.  * the bitset form, since we may wish to extend it
  554.  * in the future for other character classifications. 
  555.  *
  556.  *    TRUE for 0-9 A-Z a-z _
  557.  */
  558. static char chrtyp[MAXCHR] = {
  559.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  560.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  561.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  562.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  563.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  564.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  565.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  566.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  567.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  568.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  569.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  570.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  571.     1, 1, 1, 0, 0, 0, 0, 0
  572.     };
  573.  
  574. #define inascii(x)    (0177&(x))
  575. #define iswordc(x)     chrtyp[inascii(x)]
  576. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & (1<<((y)&BITIND)))
  577.  
  578. /*
  579.  * skip values for CLO XXX to skip past the closure
  580.  *
  581.  */
  582.  
  583. #define ANYSKIP    2     /* CLO ANY END ...       */
  584. #define CHRSKIP    3    /* CLO CHR chr END ...       */
  585. #define CCLSKIP 18    /* CLO CCL 16bytes END ... */
  586.  
  587. static char *
  588. pmatch(lp, ap)
  589. register char *lp;
  590. register CHAR *ap;
  591. {
  592.     register char *e;        /* extra pointer for CLO */
  593.     register char *bp;        /* beginning of subpat.. */
  594.     register char *ep;        /* ending of subpat..     */
  595.     register int op, c, n;
  596.     char *are;            /* to save the line ptr. */
  597.  
  598.     while ((op = *ap++) != END)
  599.         switch(op) {
  600.  
  601.         case CHR:
  602.             if (*lp++ != *ap++)
  603.                 return(0);
  604.             break;
  605.         case ANY:
  606.             if (!*lp++)
  607.                 return(0);
  608.             break;
  609.         case CCL:
  610.             c = *lp++;
  611.             if (!isinset(ap,c))
  612.                 return(0);
  613.             ap += BITBLK;
  614.             break;
  615.         case NCL:
  616.             c = *lp++;
  617.             if (isinset(ap,c))
  618.                 return(0);
  619.             ap += BITBLK;
  620.             break;
  621.         case BOL:
  622.             if (lp != bol)
  623.                 return(0);
  624.             break;
  625.         case EOL:
  626.             if (*lp)
  627.                 return(0);
  628.             break;
  629.         case BOT:
  630.             bopat[*ap++] = lp;
  631.             break;
  632.         case EOT:
  633.             eopat[*ap++] = lp;
  634.             break;
  635.          case BOW:
  636.             if (!(lp!=bol && iswordc(lp[-1])) && iswordc(*lp))
  637.                 break;
  638.             return(0);
  639.         case EOW:
  640.             if ((lp!=bol && iswordc(lp[-1])) && !iswordc(*lp))
  641.                 break;
  642.             return(0);
  643.         case REF:
  644.             n = *ap++;
  645.             bp = bopat[n];
  646.             ep = eopat[n];
  647.             while (bp < ep)
  648.                 if (*bp++ != *lp++)
  649.                     return(0);
  650.             break;
  651.         case CLO:
  652.             are = lp;
  653.             switch(*ap) {
  654.  
  655.             case ANY:
  656.                 while (*lp)
  657.                     lp++;
  658.                 n = ANYSKIP;
  659.                 break;
  660.             case CHR:
  661.                 c = *(ap+1);
  662.                 while (*lp && c == *lp)
  663.                     lp++;
  664.                 n = CHRSKIP;
  665.                 break;
  666.             case CCL:
  667.             case NCL:
  668.                 while (*lp && (e = pmatch(lp, ap)))
  669.                     lp = e;
  670.                 n = CCLSKIP;
  671.                 break;
  672.             default:
  673.                 re_fail("closure: bad dfa.", *ap);
  674.                 return(0);
  675.             }
  676.  
  677.             ap += n;
  678.  
  679.             while (lp >= are) {
  680.                 if ((e = pmatch(lp, ap)) != 0)
  681.                     return(e);
  682.                 --lp;
  683.             }
  684.             return(0);
  685.         default:
  686.             re_fail("re_exec: bad dfa.", op);
  687.             return(0);
  688.         }
  689.     return(lp);
  690. }
  691.  
  692. /*
  693.  * re_modw:
  694.  *    add new characters into the word table to
  695.  *    change the re_exec's understanding of what
  696.  *    a word should look like. Note that we only
  697.  *    accept additions into the word definition.
  698.  *
  699.  *    If the string parameter is 0 or null string,
  700.  *    the table is reset back to the default, which
  701.  *    contains A-Z a-z 0-9 _. [We use the compact
  702.  *    bitset representation for the default table]
  703.  *
  704.  */
  705.  
  706. static char deftab[16] = {    
  707.     0, 0, 0, 0, 0, 0, 377, 003, 376, 377, 377, 207,  
  708.     376, 377, 377, 007 
  709. }; 
  710.  
  711. void
  712. re_modw(s)
  713. register char *s;
  714. {
  715.     register int i;
  716.  
  717.     if (!s || !*s) {
  718.         for (i = 0; i < MAXCHR; i++)
  719.             if (!isinset(deftab,i))
  720.                 iswordc(i) = 0;
  721.     }
  722.     else
  723.         while(*s)
  724.             iswordc(*s++) = 1;
  725. }
  726.  
  727. /*
  728.  * re_subs:
  729.  *    substitute the matched portions of the src in
  730.  *    dst.
  731.  *
  732.  *    &    substitute the entire matched pattern.
  733.  *
  734.  *    \digit    substitute a subpattern, with the given
  735.  *        tag number. Tags are numbered from 1 to
  736.  *        9. If the particular tagged subpattern
  737.  *        does not exist, null is substituted.
  738.  *
  739.  */
  740. int
  741. re_subs(src, dst)
  742. register char *src;
  743. register char *dst;
  744. {
  745.     register char c;
  746.     register int  pin;
  747.     register char *bp;
  748.     register char *ep;
  749.  
  750.     if (!*src || !bopat[0])
  751.         return(0);
  752.  
  753.     while ((c = *src++) != 0) {
  754.         switch(c) {
  755.  
  756.         case '&':
  757.             pin = 0;
  758.             break;
  759.  
  760.         case '\\':
  761.             c = *src++;
  762.             if (c >= '0' && c <= '9') {
  763.                 pin = c - '0';
  764.                 break;
  765.             }
  766.             
  767.         default:
  768.             *dst++ = c;
  769.             continue;
  770.         }
  771.  
  772.         if ((bp = bopat[pin]) && (ep = eopat[pin])) {
  773.             while (*bp && bp < ep)
  774.                 *dst++ = *bp++;
  775.             if (bp < ep)
  776.                 return(0);
  777.         }
  778.     }
  779.     *dst = (char) 0;
  780.     return(1);
  781. }
  782.             
  783. #if    defined(DEBUG)
  784. /*
  785.  * symbolic - produce a symbolic dump of the
  786.  *            dfa
  787.  */
  788. symbolic(s) 
  789. char *s;
  790. {
  791.     (void)printf("pattern: %s\n", s);
  792.     (void)printf("dfacode:\n");
  793.     dfadump(dfa);
  794. }
  795.  
  796. static    
  797. dfadump(ap)
  798. CHAR *ap;
  799. {
  800.     register int n;
  801.  
  802.     while (*ap != END)
  803.         switch(*ap++) {
  804.         case CLO:
  805.             (void)printf("CLOSURE");
  806.             dfadump(ap);
  807.             switch(*ap) {
  808.             case CHR:
  809.                 n = CHRSKIP;
  810.                 break;
  811.             case ANY:
  812.                 n = ANYSKIP;
  813.                 break;
  814.             case CCL:
  815.             case NCL:
  816.                 n = CCLSKIP;
  817.                 break;
  818.             }
  819.             ap += n;
  820.             break;
  821.         case CHR:
  822.             (void)printf("\tCHR %c\n",*ap++);
  823.             break;
  824.         case ANY:
  825.             (void)printf("\tANY .\n");
  826.             break;
  827.         case BOL:
  828.             (void)printf("\tBOL -\n");
  829.             break;
  830.         case EOL:
  831.             (void)printf("\tEOL -\n");
  832.             break;
  833.         case BOT:
  834.             (void)printf("BOT: %d\n",*ap++);
  835.             break;
  836.         case EOT:
  837.             (void)printf("EOT: %d\n",*ap++);
  838.             break;
  839.         case BOW:
  840.             (void)printf("BOW\n");
  841.             break;
  842.         case EOW:
  843.             (void)printf("EOW\n");
  844.             break;
  845.         case REF:
  846.             (void)printf("REF: %d\n",*ap++);
  847.             break;
  848.         case CCL:
  849.             (void)printf("\tCCL [");
  850.             for (n = 0; n < MAXCHR; n++)
  851.                 if (isinset(ap,(CHAR)n))
  852.                     (void)printf("%c",n);
  853.             (void)printf("]\n");
  854.             ap += BITBLK;
  855.             break;
  856.         case NCL:
  857.             (void)printf("\tNCL [");
  858.             for (n = 0; n < MAXCHR; n++)
  859.                 if (isinset(ap,(CHAR)n))
  860.                     (void)printf("%c",n);
  861.             (void)printf("]\n");
  862.             ap += BITBLK;
  863.             break;
  864.         default:
  865.             (void)printf("bad dfa. opcode %o\n", ap[-1]);
  866.             exit(1);
  867.             break;
  868.         }
  869. }
  870. #endif    /* defined(DEBUG) */
  871.